/**********************************************************************/
/**  Copyright (c) ECC labs. 2001-2002. All Rights Reserved.		 **/
/**********************************************************************/
/*
	bincode.cpp
	Mark Papazyan

*/


#include "binmatrix.h"



CBinMatrix::CBinMatrix(t_len k, t_len n, int flag, int base)
	:k(k),n(n),flag(flag), base(base)
{	
	row = new(CBinWord[k]);
	col = new(CBinWord[n]);

	for(t_cnt i=0; i<k; i++)
	{
		row[i].num=(I)0;
		row[i].n=n;
	}

	for(t_cnt l=0; l<n; l++)
		col[l].n=k;

	if(flag & PERM)
	{
		dat.s = new int[n] ;
		dat.flag = new long[n];
		pos = pos1 = 0 ;
		for ( t_cnt i=0; i<n; i++ ) {
			dat.s[i]=i ;
			dat.flag[i]=(I)1<<i;
		}
	}

/*	if(flag & ROW)
		cur=row;
	else
		cur=col;
		*/
}




CBinMatrix::CBinMatrix(const CBinMatrix& t)
{
	row=new(CBinWord[k=t.k]);
	col=new(CBinWord[n=t.n]);

	flag=t.flag;
	base=t.base;

	for(t_cnt i=0; i<k; i++)
	{
		row[i].num=t.row[i].num;
		row[i].n=t.n;
	}
	
	for(t_cnt ii=0; ii<n; ii++)
		col[ii].n=t.k;

	if(t.flag&HAVE_COL)//checks if cols were made
		for(t_cnt j=0; j<n; j++)
			col[j].num=t.col[j].num;

	if(flag & PERM)
	{
		dat.s = new int[n] ;
		dat.flag = new long[n];
		pos = pos1 = 0 ;
		for ( t_cnt i=0; i<n; i++ ) {
			dat.s[i]=t.dat.s[i] ;
			dat.flag[i]=t.dat.flag[i] ;
		}
	}
}


CBinMatrix::~CBinMatrix()
{
	delete[] row;
	delete[] col;

	if(flag & PERM){
		delete[] dat.flag;
		delete[] dat.s;
	}
}


ostream& operator<<(ostream& out, CBinMatrix& a)
{
	t_cnt i=0;
	if(a.flag&ROW)
	switch(a.base){
	 case BIN:
		for(i=0; i<a.k; i++)
		{
			for(t_cnt j=0; j<a.n; j++)
			(a.row[i].num&((I)1<<(a.n-1-j)))?out<<'1':out<<'.';
			out<<'\n';
		}
		break;
	case HEX:
		for(i=0; i<a.k; i++)
			out<<"0x"<<hex<<(I)a.row[i].num<<'\n';
		break;
	 case OCT:
		 for(i=0; i<a.k; i++)
			out<<0<<oct<<(I)a.row[i].num<<'\n';
		break;
	 default:
		 for(i=0; i<a.k; i++)
			out<<(I)a.row[i].num<<'\n';
		}


	else if(a.flag&COL)
	 switch(a.base){
		 case BIN:
			for(i=0; i<a.n; i++)
			{
				for(t_cnt j=0; j<a.k; j++)
				(a.col[i].num&((I)1<<(a.k-1-j)))?out<<'1':out<<'.';
				out<<'\n';
			}
			break;
		 case HEX:
			for(i=0; i<a.n; i++)
				out<<"0x"<<hex<<(I)a.col[i].num<<'\n';
			break;
		 case OCT:
			 for(i=0; i<a.n; i++)
				out<<0<<oct<<(I)a.col[i].num<<'\n';
			break;
		 default:
			 for(i=0; i<a.n; i++)
				out<<(I)a.col[i].num<<'\n';
			}

	return out;
}




istream& operator>>(istream& in, CBinMatrix& a)
{
	t_cnt i=0;
	string s;
	if(a.flag & ROW)
	{
		if(a.base==BIN)
			for(i=0; i<a.k; i++)
			{
				in>>s;
				a.row[i].num=a.row[i].bin2dec(s);
			}
		else
			for(i=0; i<a.k; i++)
				in>>a.row[i].num;
	}

	else if(a.flag&COL)
	{
		if(a.base==BIN)
			for(i=0; i<a.n; i++)
			{
				in>>s;
				a.col[i].num=a.col[i].bin2dec(s);
			}
		else
			for(i=0; i<a.n; i++)
				in>>a.col[i].num;
	}

	return in;
}





CBinMatrix& CBinMatrix::operator=(const CBinMatrix& t)
{
	if(this!=&t)
	{
		delete[] row;
		delete[] col;
		
		if(flag & PERM){
			delete[] dat.s;
			delete[] dat.flag;
		}

		row=new(CBinWord[k=t.k]);
		col=new(CBinWord[n=t.n]);

		flag=t.flag;
		base=t.base;

		for(t_cnt i=0; i<k; i++)
		{
			row[i].num=t.row[i].num;
			row[i].n=n;
		}

		for(t_cnt ii=0; ii<n; ii++)
			col[ii].n=k;

		if(t.flag&HAVE_COL)//checks if cols were made
			for(t_cnt j=0; j<n; j++)
				col[j].num=t.col[j].num;

		if(t.flag & PERM)
		{
			dat.s = new int[n] ;
			dat.flag = new long[n];
			pos = pos1 = 0 ;
			for ( t_cnt i=0; i<n; i++ ) {
				dat.s[i]=t.dat.s[i] ;
				dat.flag[i]=t.dat.flag[i] ;
			}
		}

	}

	return *this;
}




CBinWord CBinMatrix::operator*(CBinWord& a)
{
	CBinWord res(k);
	row2col();
	for(t_cnt i=n-1; i>=0; i--)
		if(a.num>>i&(I)1)res.num^=col[i].num;
	return res;
}




CBinWord CBinMatrix::operator*(t_src a)
{
	CBinWord res(k);
	row2col();
	for(t_cnt i=n-1; i>=0; i--)
		if(a>>i&(I)1)res.num^=col[i].num;
		return res;
}



CBinMatrix CBinMatrix::operator^(CBinMatrix &b)
{
	CBinMatrix C(k*b.k, n*b.n);

	for(t_cnt i=0; i<k; i++)
		for(t_cnt j=0; j<b.k; j++)
			C.row[i*b.k+j]=row[i]^b.row[j];

	return C;
}


CBinMatrix CBinMatrix::operator^(CBinWord &b)
{
	CBinMatrix C(k, n*b.n);
	for(t_cnt i=0; i<k; i++)
		C.row[i]=row[i]^b;

	return C;
}


//multiplication of matrix
CBinMatrix CBinMatrix::operator*(CBinMatrix &b)
{
	CBinMatrix C(k, b.n);

	row2col();
	b.row2col();
	for(t_cnt j=b.n-1; j>=0; j--)
		for(t_cnt i=n-1; i>=0; i--)
			if(b.col[j].num>>i&(I)1)C.col[j].num^=col[i].num;
		
	C.col2row();

	return C;
}

CBinMatrix CBinMatrix::operator +(CBinMatrix& a)
{
	CBinMatrix c=*this;
	return c+=a;
}

CBinMatrix& CBinMatrix::operator ^=(CBinWord& a)
{
	return (*this=*this^a);
}

CBinMatrix& CBinMatrix::operator *=(CBinMatrix& a)
{
	return (*this=*this*a);
}

CBinMatrix& CBinMatrix::operator ^=(CBinMatrix& a)
{
	return (*this=*this^a);
}

CBinMatrix& CBinMatrix::operator +=(CBinMatrix& a)
{
	for(t_cnt i=0; i<k; i++)
		row[i].num^=a.row[i].num;

	return *this;
}

void CBinMatrix::trans()
{
	CBinMatrix tmatr(n, k, flag);
	for(t_cnt i=0; i<n; i++)
		for(t_cnt j=0; j<k; j++)
			((i-j-n+k>=0)?
			(tmatr.row[i].num|=(row[j].num&((I)1<<(n-i-1)))<<(i-j-n+k))
			:(tmatr.row[i].num|=(row[j].num&((I)1<<(n-i-1)))>>(j-i+n-k)));

		*this=tmatr;
	
}



void CBinMatrix::row2col()//first right col will become first row 
{
	if(!(flag&HAVE_COL))set_hcol();//putting flag number that indicates creation of cols

	for(t_cnt i=0; i<n; i++){
		col[i].num=(I)0;
		for(t_cnt j=0; j<k; j++)
		//	col[i].num|=(((row[j].num>>i)&(I)1)<<(k-1-j));	
			if(row[j].is_set(i))
				col[i].bit_set(j);
	}
}



void CBinMatrix::col2row()
{
	for(t_cnt j=0; j<k; j++)
	{
		row[j].num=(I)0;
		for(t_cnt i=0; i<n; i++)
			if(col[i].is_set(j))
				row[j].bit_set(i);
	}
}



t_res CBinMatrix::edin(char ch)
{
	CBinMatrix  TEMP(k, n);
	for(t_cnt x=0; x<k; x++)
		TEMP.row[x]=row[x];//temporary class
	

	t_len t=0,i=0;
	t_src check=(I)0;

	while(i<k)
	{
		if(row[i].num&((I)1<<(n-t-1))) //found 1
			{
				for(t_cnt h=i+1; h<k; h++)
					if(row[h].num&((I)1<<(n-t-1)))
						row[h].num^=row[i].num; //adding string if 1
				
				check^=((I)1<<(n-1-t));			//check indicates those positions where 1 is(by putting in this position 1)
				t++;
				i++;
			}
	
		else
		{
			t_len h=i+1;
			while((!(row[h].num&((I)1<<(n-t-1))))&&(h<k))
			    h++;		
			(h==k)?t++: row[i].num^=row[h].num;
			if(t>=n)
			{			//not linear dependent case
				for(t_cnt x=0; x<k; x++)
					row[x]=TEMP.row[x];

				return 0;
			}
		}
	}

//annulating above
		int val=k-2;
			for(i=0; i<n-1; i++)
				if(check>>i&(I)1)
				{
					for(t_cnt h=val; h>=0; h--)
					if((row[h].num&((I)1<<i))) row[h].num^=row[val+1].num;
					val--;
				}

//arranging by gathering single matrix to left/right

		row2col();

		t_len m=0; 
		if(ch=='l') //by default gathering single matrix to left
		{	
			for(t_cnt c=0; c<n; c++)
				if(check>>(n-1-c)&(I)1)
				{
					CBinWord tmp=col[n-1-c];
					col[n-1-c]=col[n-1-m];
					col[n-1-m]=tmp;
					m++;
				}
		}
		else if(ch=='r') //when ch='r' gathering single matrix to right
		{	
			for(t_cnt c=0; c<n; c++)
				if(check>>c&(I)1)
				{
					CBinWord tmp=col[c];
					col[c]=col[m];
					col[m]=tmp;
					m++;
				}
		}

	col2row();
	return 1;
}




CBinWord CBinMatrix::gaus()
{
	t_len t=0,i=0;
	CBinWord check(n);

	while(i<k)
	{
		if(row[i].num&((I)1<<(n-t-1))) //found 1
			{
				for(t_cnt h=i+1; h<k; h++)
					if(row[h].num&((I)1<<(n-t-1)))
						row[h].num^=row[i].num; //adding string if 1
				
				check.num^=((I)1<<(n-1-t));			//check indicates those positions where 1 is(by putting in this position 1)
				t++;
				i++;
			}
	
		else
		{
			t_len h=i+1;
			while((h<k) && (!(row[h].num&((I)1<<(n-t-1)))))
			    h++;		
			(h==k)?t++: row[i].num^=row[h].num;
			if(t>=n)
			{		
			//	cerr<<"ERROR: LINEAR DEPENDANT\n";
				return check;
			}
		}
	}

	return check;
}



CBinWord CBinMatrix::col_gaus()
{
	row2col();
	t_len t=0,i=0;
	CBinWord check(k);

	while(i<n)
	{
		if(col[i].num&((I)1<<(k-t-1))) //found 1
			{
				for(t_cnt h=i+1; h<n; h++)
					if(col[h].num&((I)1<<(k-t-1)))
						col[h].num^=col[i].num; //adding string if 1
				
				check.num^=((I)1<<(k-1-t));			//check indicates those positions where 1 is(by putting in this position 1)
				t++;
				i++;
			}
	
		else
		{
			t_len h=i+1;
			while((h<n) && (!(col[h].num&((I)1<<(k-t-1)))))
			    h++;		
			(h==n)?t++: col[i].num^=col[h].num;
			if(t>=k){
				col2row();
				return check;
			}
		}
	}
	col2row();
	return check;
}



void CBinMatrix::cyclic_shift(t_len y, char where)
{
	for(t_cnt i=0; i<k; i++)
		row[i].cyclic_shift(y, where);

}


void CBinMatrix::mixer()
{
	if(!(flag & PERM))
	{
		dat.s = new int[n] ;
		dat.flag = new long[n];
		pos = pos1 = 0 ;

		for ( t_cnt i=0; i<n; i++ ) {
			dat.s[i]=i ;
			dat.flag[i]=(I)1<<i;
		}

		flag^=PERM;
	}
	//finding
	t_len i=n-1;
	while((dat.s[i]<dat.s[i-1]) && i>0)i--;

	t_len g=i-1; 
	if(g!=-1)
	{
		int temp=dat.s[g];
		t_len h=n-1;

		while((h>g) && (temp>dat.s[h]))
			h--;
		dat.s[g]=dat.s[h];
		dat.s[h]=temp;
	
		int tmp;
		//resorting
		for(t_cnt m=g+1; m<(n+g-1)/2+1; m++)
		{
			tmp=dat.s[n-m+g]; // just swapping
			dat.s[n-m+g]=dat.s[m];
			dat.s[m]=tmp;
		}

		
		//series[n-h+g]=temp;
		
	}

 CBinWord* temp=new CBinWord[n];
 row2col();

 for(t_cnt l=0; l<n; l++)
	temp[l].num=col[dat.s[l]].num;

  for(t_cnt ll=0; ll<n; ll++)
   col[ll].num=temp[ll].num;

 col2row();
 delete[] temp;
 
}


void CBinMatrix::set_col()
{
	flag^=COL^ROW;
}

void CBinMatrix::set_hcol()
{
	flag^=HAVE_COL;
}

void CBinMatrix::set_row()
{
	flag^=COL^ROW;
}


void CBinMatrix::set_base(int i){base=i;}


t_src CBinMatrix::gaus1(){

    t_len main_var = 0 ;
    
    for( t_cnt i=0; i<k; i++ ){
        for( t_cnt j=i; j<n; ){
            if( row[i].is_set(j) ){
                main_var|=(I)1<<j ;
                for( t_cnt t=i+1; t<k; t++ ){
                    if( row[t].is_set(j) )
                        row[t].num^=row[i].num ;       
                }
                break ;
            }
            else{
                t_cnt t=i+1;
                for( ; t<k; t++ ){
                    if( row[t].is_set(j) ){
                        row[i].num^=row[t].num ;    
                        main_var|=(I)1<<j ;
                        break ;
                    }
                }
                if( t==k ) j++ ;
            }
        }
    }
return main_var ;                                
}



t_src CBinMatrix::col_step(){

    t_len main_var = 0 ;
    row2col();
    for( t_cnt i=0; i<n; i++ ){
        for( t_cnt j=i; j<k; ){
            if( col[i].is_set(j) ){
                main_var|=(I)1<<j ;
                for( t_cnt t=i+1; t<n; t++ ){
                    if( col[t].is_set(j) )
                        col[t].num^=col[i].num ;       
                }
                break ;
            }
            else{
                t_cnt t=i+1;
                for( ; t<n; t++ ){
                    if( col[t].is_set(j) ){
                        col[i].num^=col[t].num ;    
                        main_var|=(I)1<<j ;
                        break ;
                    }
                }
                if( t==n ) j++ ;
            }
        }
    }
	col2row();
return main_var ;                                
}


void CBinMatrix::print(){

	for (t_cnt i=0; i<n; i++)
		cout << dat.s[n-i-1];
		cout <<'\n';
}


t_res CBinMatrix::next() {

	if(!(flag & PERM))
	{
		dat.s = new int[n] ;
		dat.flag = new long[n];
		pos = pos1 = 0 ;

		for ( t_cnt i=0; i<n; i++ ) {
			dat.s[i]=i ;
			dat.flag[i]=(I)1<<i;
		}

		flag^=PERM;
	}
		pos1=0 ;
		while( dat.flag[pos] & ( (I)1 << dat.s[pos1] )) pos1++ ;

		if ( pos1 < pos ) {
			dat.flag[pos] |= ( (I)1 << dat.s[pos1] ) ;
			dat.flag[pos1] = (I)1<<dat.s[pos] ;
			tr[0] = pos1 ;
			tr[1] = pos ;
			transp() ;
			pos = 0 ;
			return 0 ;
		}
		else if ( pos < n-1 ) {
						dat.flag[pos] = (I)1<<dat.s[pos] ;
						pos++ ;
						return next() ;
					}
		else return 1 ;
}


inline void CBinMatrix::transp(){

	if(!(flag & PERM))
	{
		dat.s = new int[n] ;
		dat.flag = new long[n];
		pos = pos1 = 0 ;

		for ( t_cnt i=0; i<n; i++ ) {
			dat.s[i]=i ;
			dat.flag[i]=(I)1<<i;
		}

		flag^=PERM;
	}

		t_src temp = dat.s[pos1] ;
		dat.s[pos1] = dat.s[pos] ;
		dat.s[pos] = temp ;
}


t_res CBinMatrix::col_swap() {

		for( t_cnt i=0; i<k; i++ )
			row[i].bit_swap(tr[0], tr[1]);

		return 0 ;
}



t_res CBinMatrix::swap () {

	if(!(flag & PERM))
	{
		dat.s = new int[n] ;
		dat.flag = new long[n];
		pos = pos1 = 0 ;

		for ( t_cnt i=0; i<n; i++ ) {
			dat.s[i]=i ;
			dat.flag[i]=(I)1<<i;
		}

		flag^=PERM;
	}

		for ( t_cnt i=0; i<k; i++ ) {
			t_src temp = 0 ;
			for ( t_cnt i=0; i<n; i++ ) {
				if( ((I)1<<i) & row[i].num ) {
					temp^=((I)1<<dat.s[i]) ;
				}
			}
			row[i].num = temp ;
		}
		return 0;
}



void add_mat(CBinMatrix& a, CBinMatrix& b, CBinMatrix& c)
{
	if(a.k==b.k && b.k==c.k)
		for(t_cnt i=0; i<b.k; i++)
			a.row[i].num=b.row[i].num^c.row[i].num;
}

void mul_mat(CBinMatrix& a, CBinMatrix& c, CBinMatrix& b)
{
	c.row2col();
	b.row2col();
	
	for(t_cnt j=b.n-1; j>=0; j--)
		for(t_cnt i=c.n-1; i>=0; i--)
			if(b.col[j].num>>i&(I)1)a.col[j].num^=c.col[i].num;

	a.col2row();
}

void mul_vec(CBinWord& a, CBinMatrix& c, CBinWord& b)
{
	c.row2col();
	for(t_cnt i=c.n-1; i>=0; i--)
		if(b.num>>i&(I)1)a.num^=c.col[i].num;
}

void tmul_mat(CBinMatrix& a, CBinMatrix& c, CBinMatrix& b)
{
	for(t_cnt i=0; i<c.k; i++)
		for(t_cnt j=0; j<b.k; j++)
			a.row[i*b.k+j]=c.row[i]^b.row[j];
}

void tmul_vec(CBinMatrix& a, CBinMatrix& c, CBinWord& b)
{
	for(t_cnt i=0; i<c.k; i++)
		a.row[i]=c.row[i]^b;

}

